import math

device_name = input('Please enter Device file name:')

# 电池坐标
battery = []

# 其他设备坐标
devices = []

with open(device_name) as f:
    lines = f.readlines()
    # 得到电池坐标
    battery_points_str = lines[:1][0].replace('\n', '')
    battery_points = battery_points_str.split('-')
    for point in battery_points:
        battery.append(point)
    # 得到设备坐标
    devices_points = lines[1:]
    for point in devices_points:
        devices.append(point.replace('\n', ''))
f.close()


connect_name = input('Please enter a connection file name: ')

#  生成所有的连接数，将连接数添加到这个集合中
connections = []


# 递归生成所有的连接数
# 6,8 2,6
# 2,6 3,0
# 6,4 7,8
# 6,4 4,3
# 3,0 4,3
# 电池坐标开始是 6,8 然后就能找到2,6，通过2,6，就能找到3,0 依次类推，得到一个顺序集合
def search_point(lines, point):
    if len(lines) == 0:
        return battery[1]
    for line in lines:
        if point in line:
            connections.append(point)
            points = line.split(' ')
            for other_point in points:
                if other_point != point:
                    lines.remove(line)
                    return search_point(lines, other_point)


with open(connect_name) as f:
    origin_line = f.readlines()
    lines = []
    for line in origin_line:
        lines.append(line.replace('\n', ''))
    # 从电池坐标开始
    connections.append(search_point(lines, battery[0]))
f.close()


# 2点之间距离方法
def get_instance(point_one, point_two):
    point_one_x_y = point_one.split(',')
    point_two_x_y = point_two.split(',')
    x = int(point_one_x_y[0]) - int(point_two_x_y[0])
    y = int(point_one_x_y[1]) - int(point_two_x_y[1])
    return math.sqrt((x ** 2) + (y ** 2))

# 去掉顺序集合中的一个点，求出来的cost
def get_all_instance(new_connections):
    sum = 0
    for i in range(len(new_connections)):
        if i == len(new_connections) - 1:
            break
        sum = sum + get_instance(new_connections[i], new_connections[i + 1])
    return sum


# 冒泡排序求出最小的长度
def sort_min_cost(all_remove_list):
    for i in range(len(all_remove_list)):
        for j in range(i):
            if all_remove_list[j]['distance'] > all_remove_list[j + 1]['distance']:
                all_remove_list[j], all_remove_list[j + 1] = all_remove_list[j + 1], all_remove_list[j]


all_remove_list = []

# 每移除一个点，就求一次和，起点和终点不用移除
for remove_point in devices:
    new_connections = []
    dict = {}
    for conn in connections:
        if conn != remove_point:
            new_connections.append(conn)
    dict['remove'] = remove_point
    sum = round(get_all_instance(new_connections), 2)
    dict['distance'] = sum
    all_remove_list.append(dict)

# 开始排序
sort_min_cost(all_remove_list)

print('of the connections and device given')

# 排序之后第一个就是最小的
min_connect = all_remove_list[0]

print('[',min_connect['remove'],']','should be removed')

total_cost = get_all_instance(connections)
min_cost = min_connect['distance']
print('this saves ',round(total_cost-min_cost,2),'mm of writing')
